﻿//简单短小的函数和模版函数需要声明和定义放在一起。
//长的函数和需要隐藏细节的函数就把声明和定义分离
#pragma once
#include<iostream>
#include<vector>
#include<ctime>
#include<cassert>
#include<thread>
#include<mutex>
#include<atomic>
#include<algorithm>
#include<unordered_map>
#include<ctime>
#include<cstdlib>
#ifdef _WIN32
#include<windows.h>
#else
#include <sys/mman.h>  // 提供 mmap/munmap 声明
#include <unistd.h>    // 提供系统常量（如PROT_READ）
#include <cstdint>  // 保证 uint64_t 和 uint32_t 的定义
#endif

// 直接去堆上按⻚申请空间 
inline static void* SystemAlloc(size_t kpage){
	//虽然实际是4KB为1页，但是我们选择8KB为一页
	void* ptr = nullptr;
#ifdef _WIN32
	ptr = VirtualAlloc(
		0,                      // [输入] lpAddress: 期望的内存起始地址，0表示由系统自动选择
		kpage * (1 << 13),      // [输入] dwSize: 要分配的内存大小（字节数），这里计算kpage个8KB（1<<13=8192字节）
		MEM_COMMIT | MEM_RESERVE, // [输入] flAllocationType: 分配类型标志
		//   MEM_RESERVE - 保留虚拟地址空间
		//   MEM_COMMIT - 同时提交物理存储（内存或页面文件）
		PAGE_READWRITE          // [输入] flProtect: 内存保护标志，PAGE_READWRITE表示可读可写
	);
#else
	// linux下brk mmap等 
	//使用mmap申请匿名内存（无需文件映射）
	ptr = mmap(
		0,                                  // 由内核选择地址
		kpage * (1 << 13),                  // 分配大小（1页=8KB）
		PROT_READ | PROT_WRITE,             // 可读可写
		MAP_PRIVATE | MAP_ANONYMOUS,        // 匿名映射（不关联文件）
		-1,                                 // 文件描述符（匿名映射时设为-1）
		0                                   // 偏移量（匿名映射时忽略）
	);
	if (ptr == MAP_FAILED) ptr = nullptr; // 失败时设为nullptr，与Windows保持一致
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
inline static void SystemFree(void* ptr){
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等 
	munmap(ptr, kpage * (1 << 13));
#endif
}


using std::cout;
using std::endl;
//因为如果地址是2^64 每个页如果是8KB（2^13）  页数理论上有2^51 
//32位环境下只有WIN32  而64位环境下WIN64和WIN32都有,因此要把WIN64放前面
#ifdef _WIN64
typedef uint64_t PAGE_ID;  // Windows 64位
#elif _WIN32
typedef uint32_t PAGE_ID;  // Windows 32位
#else
	// Linux/Unix/其他平台
#if defined(__x86_64__) || defined(__aarch64__) || defined(__LP64__)
typedef uint64_t PAGE_ID;  // 64位架构（x86_64/ARM64等）
#else
typedef uint32_t PAGE_ID;  // 默认32位（x86/ARM等）
#endif
#endif

//这个函数在CentrealCache和ThreadCache里面都会用到
static inline void*& NextObj(void* obj) {
	return *(void**)obj;//取obj的头指针个字节 &是为了直接修改
}
//自由链表
class FreeList {
public:
	//插入到自由链表
	void Push(void* obj) {
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	//插入一个范围的链表(n块)
	void PushRange(void* start, void* end, size_t n) { 
		NextObj(end) = _freeList;
		_freeList = start;
		//条件断点+测试
	/*	void* cur = start;
		int i = 0;
		while (cur) {
			cur = NextObj(cur);
			++i;
		}
		if (n != i) {
			int x = 0;
		}*/
		_size += n;
	}
	//从自由链表中取一块出去用
	void* Pop() {
		assert(_freeList);
		void* obj = _freeList;//先记录下来
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}
	//弹出一个范围的链表准备拿出去准备归还(n块)
	void PopRange(void*& start, void*& end, size_t n) {
		assert(n <= _size);
		start = _freeList;
		end = start;
		for (int i = 0; i < n - 1; ++i){
			end = NextObj(end);
			assert(end);
		}
		//此时end走到我们想要的最后一块
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	bool Empty() {return _freeList == nullptr;}
	size_t& GetMaxsize() {return _maxSize;}
	size_t GetSize() { return _size; }
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;//慢启动阈值 一次批量生成的块数
	size_t _size = 0;//统计当前自由链表里面有多少块
};


// ⼩于等于MAX_BYTES，就找thread cache申请 
// ⼤于MAX_BYTES，就直接找page cache或者系统堆申请 
static const size_t MAX_BYTES = 256 * 1024;
// thread cache 和 central cache自由链表哈希桶的表⼤⼩ 
static const size_t NFREELISTS = 208;
// page cache 管理span list哈希表⼤⼩ 
static const size_t NPAGES = 129;
// 页大小转换偏移, 即⼀⻚定义为2^13,也就是8KB 
static const size_t PAGE_SHIFT = 13;


// 管理对齐和映射等关系
class SizeClass {
public:
	//因为如果按照8byte对齐，得需要几万个桶，所以我们必须设计一种新的对齐方式
	// 整体控制在最多10%左右的内碎片浪费 
	// [1,128] 8byte对齐 freelist[0,16) 
	// [128+1,1024] 16byte对齐 freelist[16,72) 
	// [1024+1,81024] 128byte对齐 freelist[72,128)
	// [8*1024+1,641024] 1024byte对齐 freelist[128,184) 
	// [64*1024+1,256*1024] 8*1024byte对齐 freelist[184,208) 
 
	//通过bytes计算  对齐大小的计算
	static inline size_t RoundUp(size_t size) {
		if (size <= 128) return _RoundUp(size, 8);
		else if (size <= 1024) return _RoundUp(size, 16);
		else if (size <= 1024 * 8) return _RoundUp(size, 128);
		else if (size <= 1024 * 64) return _RoundUp(size, 1024);
		else if (size <= 1024 * 256) return _RoundUp(size, 8 * 1024);
		else return _RoundUp(size,1<<PAGE_SHIFT);//按页对齐
		return -1;
	}
	//通过bytes计算 计算出桶号
	static inline size_t Index(size_t size) {
		assert(size <= MAX_BYTES);
		// 每个区间有多少个链 
		static int group_array[4] = { 16, 56, 56, 56 };
		if (size <= 128) return _Index(size, 8);
		else if (size <= 1024) return _Index(size - 128, 16)+ group_array[0];
		else if (size <= 1024 * 8) return _Index(size -1024, 128)+ group_array[0]+ group_array[1];
		else if (size <= 1024 * 64) return _Index(size -8*1024, 1024) + group_array[0] + group_array[1]+ group_array[2];
		else if (size <= 1024 * 256) return _Index(size -64*1024, 8 * 1024) + group_array[0] + group_array[1] + group_array[2]+ group_array[3];
		else assert(false);
		return -1;
	}
	// thread cache一次从central cache中获取多少个size大小的块
	static size_t NumMoveSize(size_t size){
		assert(size > 0);
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		size_t num = MAX_BYTES / size;
		if (num < 2) num = 2;
        else if (num > 512) num = 512;
		return num;
	}
	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size){
		size_t num = NumMoveSize(size);//因为你一次要这么多，所以我尽量满足你
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;//需要申请的页数
		if (npage == 0)  npage = 1;//8bytes*512=4096bytes=0.5Page
		return npage;
	}
	//通过size+对齐数 计算大小
	static inline size_t _RoundUp(size_t size, size_t AlignNum) {
		if (size % AlignNum) return (size / AlignNum + 1) * AlignNum;
		else return size;
		//return (((size)+AlignNum - 1) & ~(AlignNum - 1)); 特殊玩法
	}
	//通过对齐后的size+对齐数 计算是第几个桶
	static inline size_t _Index(size_t size, size_t AlignNum) {//7/8=1  8/8=1
		if (size % AlignNum == 0)return size / AlignNum - 1;
		else return size / AlignNum;
	}
};


//管理多个连续页大块内存跨度结构
struct Span {
	PAGE_ID _pageId = 0;//大块内存起始页的页号
	size_t _n = 0;//页的个数
	Span* _prev = nullptr;
	Span* _next = nullptr;
	size_t _objsize = 0;//切好的小对象的大小
	size_t _useCount = 0; // 切好小块内存，被分配给thread cache的计数 用来判断释放时机
	void* _freeList = nullptr;  // 切好的小块内存的自由链表
	bool _isUse = false; //是否在被使用
};

//带头双向循环链表
class SpanList {
public:
	SpanList() {
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}
	//为了方便遍历
	Span* Begin() {return _head->_next;}
	Span* End() {return _head;}
	//判断当前Span是否有东西
	bool Empty() {return _head == _head->_next;}
	void PushFront(Span* newSpan) {Insert(Begin(), newSpan);}
	Span* PopFront(){
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	void Insert(Span*pos, Span* newSpan) {
		assert(pos&&newSpan);
		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void Erase(Span*pos) {
		assert(pos);
		//条件断点（不能是空语句）
		if (pos == _head) {
			cout << "删头啦！你的代码有问题" << endl;
		}
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;
	}
	std::mutex& Getmtx() {return _mtx;}
private:
	Span* _head;
	std::mutex _mtx;//桶锁
};